\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}

%
\begin{document}

\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 4\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{ \{jianchan,sanjian,yemingf\}}@\itshape{cis.upenn.edu}
\end{center}

\vspace {0.25cm}
\vspace{0.25cm}

\noindent
{\bf Problem B1.} \\

\noindent
\textbf{(i) Proof:}\\

\noindent Firstly show that pumping lemma holds for $L$. Choose
$m=8$. $\forall w \in \Sigma^*$, $w\in L$, $|w|\ge m$, there are two
cases:
\begin {enumerate}

\item If there are adjacent SAME symbols in the first $8$ symbols,
decompose $w$ as $uxv$, $x$ is one of the adjacent same symbols, $u$
and $v$ are chosen so that $w=uxv$. Now $|x|=1$, $|ux|\le m$, for
$ux^iv$,

\begin {itemize}
    \item If $i=0$, since $x$ is one of the adjacent same symbols,
    one of $x$'s neighbors must also be $x$, so that $uv$ still
    has the same number of $(a^+b^+)$ components as $w$. So
    $ux^iv=uv\in L$.

    \item If $i\ge 1$, $x^i$ falls to the same $(a^+b^+)$ component as $x$. By definition of
    $L$, $ux^iv\in L$.
\end {itemize}

\item If there are NOT adjacent SAME symbols in the first $8$ symbols,
so $w=abababab\cdot\cdot\cdot$, which has $n$ $(a^+b^+)$ components,
$n\ge 4$.
\begin {itemize}
    \item If $(n-1)$ is prime, so $(n-1)$ is odd, then $n$ is even.
    Decompose $w$ as $uxv$, $u=\epsilon$, $x=abab$, $v$ is chosen
    so that $uxv=w$. For $ux^iv$, $\forall i\ge 0$, $ux^iv=(abab)^iv$, which has
    $(n-2+2i)$ $(a^+b^+)$ components. Since $(n-2+2i)$ is odd, not
    prime, so that $ux^iv\in L$.

    \item If $(n-1)$ is not prime, decompose $w$ as $uxv$, let
    $u=a$, $x=b$, $v$ is chosen so that $uxv=w$. For $ux^iv$, if
    $i=0$, $ux^iv=aababab\cdot\cdot\cdot$, which has $(n-1)$
    $(a^+b^+)$ components. Since $(n-1)$ is not prime, $ux^iv\in
    L$. If $i\ge 1$, $ux^iv=ab^+ababab\cdot\cdot\cdot$, which has
    the same number of $(a^+b^+)$ components as $w$. Since $w\in L$,
    $ux^iv\in L$.
\end {itemize}
\end {enumerate}
According to the discussion above, pumping lemma holds for $L$.\\

In the following, we will show that $L$ is not regular language.\\

Assume $L$ is regular language, according to Myhill-Nerode, L is the union of finite index of some equivalence classes.\\

For strings $w$ in $\{w \mid \ \exists n \geq 1,\, \exists x_i\in a^+,\,\exists y_i\in b^+,\, 1\leq i \leq n,\, \hbox{n is not prime}, w = x_1y_1 \cdots x_ny_n\}$, according to pigeon-hole principle, there must be two string $w_1,w_2$ belong to the same equivalence class. $w_1= x_1y_1 \cdots x_my_{m}$, $w_2= x_1y_1 \cdots x_ny_{n}$, and $m<n$, $s=n-m$.\\

Let $p$ to be the first prime larger than $m$, considering the following $p$ pairs: $(p,p+s) \cdots ( p+ ps -s, p+ps)$. \\

(1) Since $p+ps$ is not prime, check $p+ ps -s$, if $p+ ps -s$ is prime, consider the two string $w'_1=x_1y_1 \cdots x_{m+p-m+ps-s}y_{m+p-m+ps-s}$, $w'_2=x_1y_1 \cdots x_{n+p-m+ps-s}y_{n+p-m+ps-s}$, since the equivalent relationship is right-invariant, then it contradicts with the fact that $L$ is regular.\\

(2) if $p+ ps -s$ is not prime, then go recursively check the pairs above, since $p$ is prime, then we can evetually find a pair (p+is-s, p+is), where one is prime and the other is not, similarly, consider the two string $w'_1=x_1y_1 \cdots x_{m+p-m+is-s}y_{m+p-m+is-s}$, $w'_2=x_1y_1 \cdots x_{n+p-m+is-s}y_{n+p-m+is-s}$, since the equivalent relationship is right-invariant, then it contradicts with the fact that $L$ is regular.\\

\noindent
\textbf{(ii) Proof:}\\

Assume DFA $D = (Q,\Sigma,\delta,q_0,F)$ accepts $L$, let $m$ be the number of the states of $D$. Then for every $y \in \Sigma^*$ and $|y| = m$, 
notice that there are $m+1$ states on the path defined by $y$. It follows from pigeonhole principle that at least two
of the $m+1$ states are the same. We define the substring of $y$ which locates between these two identical states as 
string $x$, and write $y$ as $y = uxv$, notice that $u$ and $v$ are fixed once we define $x$.\\
Next we show the $u,v,x \in \Sigma^*$ we found satiesfied the three properties defined in the pumping lemma.
\begin{itemize}
  \item $y = uxv$. From our definition, once we locate $x$, then $u$ is the prefix of $y$ and $v$ is the suffix of $y$,
  respective to $x$. So obviously $y = uxv$.
  \item $x \neq \epsilon$. $x$ is the string locates between the two identical states on the path of $y$, it cannot be
  empty string, otherwise it contradicts the fact that there are no $\epsilon$-transitions in DFA.
  \item For all $z\in \Sigma^*$, $yz \in L$ iff $ux^ivz \in L$ for all $i \geq 0$. We prove this by showing that $\delta^*(q_0,y) 
  = \delta^*(q_0,ux^iv)$ for all $i \geq 0$. In fact this is trivial if we notice $x$ is actually a loop which locates between two identical
  states on path $y$. No matter how many times(or even zero time) we go through the loop, it really does not change the destination state. That
  is why $\delta^*(q_0,y) = \delta^*(q_0,ux^iv)$ holds for all $i \geq 0$.\\
  Hence $yz \in L$ \\
  iff $\delta^*(\delta^*(q_0,y),z) \in F$\\
  iff $\delta^*(\delta^*(q_0,ux^iv),z) \in F$\\
  iff $ux^ivz \in L$.
\end{itemize}

\medskip
(iii)
Prove that the converse of the pumping lemma in (ii) also holds,
i.e., if a language $L$ satisfies the pumping lemma in (ii),
then it is regular.\\

\noindent
\textbf{(iii) Proof:}\\

Since the language satisfies the pumping lemma in (ii), it also satisfies the following equivalent statement:\\

There is some $m \geq 1$ so that for every $y\in \Sigma^*$, if $|y|=m$, then there exist $u, x, v\in \Sigma^*$ so that:

\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\item[(3)]
For all $\alpha, \beta \in \Sigma^*$,
\[y\alpha\beta \in L
\quad\hbox{iff}\quad
ux^iv\alpha\beta\in L\]
for all $i\geq 0$.
\end{enumerate}

Similar to property (3), we can define an equivalence relationship:

\begin{center}
$u \sim v$ if and only if, for all $\alpha \in \Sigma^*$, $u\alpha \in L \quad\hbox{iff}\quad v\alpha \in L$
\end{center}

We can easily show that $\sim$ is an right invariant equivalence relation: if $u \sim v$, we just rewrite the $\alpha$ as $w\alpha $,
then we have $uw \sim vw$\\


(1) For all string $y' \in L$, $|y'|<m$, they belong to at most $|\Sigma|^m$ equivalence classes in $\sim$.\\

(2) For all string $y \in L$, $|y| \geq m$, since pumping lemma holds, there exits $y=uxv$, for $\alpha = \epsilon \in \Sigma^*$, $y\alpha \in L \quad\hbox{iff}\quad ux^0v\alpha\in L$, and $|uv|<|y|$, by recursively apply such method, we can find $y' \in L$, $|y'|<m$, and $y \sim y'$. \\

With (1)(2), then we have $L$ belongs to the union of finite index of equivalence classes in $\sim$. Finally we show $L$ is exactly union of 
finite index of equivalence classes in $\sim$:\\

(3) For every equivalence class $C_{\sim}$ in $\sim$, if there exits one string $y \in C_{\sim}$ and $y \in L$, since $\sim$ is right invariant and property (3) hold, then we have all the strings in $C_{\sim}$ belong to $L$.\\

With (1)(2)(3), then we have $L$ is equal to the union of finite index of equivalence classes in $\sim$.\\ 

According to \textbf{Myhill-Nerode Theorem}, $L$ is regular language.\\

\medskip
(iv)
Consider yet another version of the pumping lemma.
For any regular language $L$, there is some $m \geq 1$ so that
for every $y\in \Sigma^*$, if $|y| \geq m$, then there exist
$u, x, v\in \Sigma^*$ so that
\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\item[(3)]
For all $\alpha, \beta\in \Sigma^*$,
\[\alpha u\beta \in L
\quad\hbox{iff}\quad
\alpha ux^i \beta\in L\]
for all $i\geq 0$.
\end{enumerate}

Prove that this pumping lemma holds.\\

\noindent
\textbf{(iv) Proof:}\\

Give DFA $D=(Q,\Sigma,\delta,q_{0},F)$ of regular language $L$, We firstly define an equivalent relationship:
$$x \sim y\quad\hbox{if and only if},\quad\hbox{for all}\quad p\in Q,\quad \delta^{*}(p,x) = \delta^{*}(p,y).$$
In \textbf{Homework 3 Problem B2}, we already prove that $\sim$ is an equivalence relation that is both left and right invariant, and $\sim$ has at most $n^{n}$ equivalence classes.

Let $m>n^n$, for every string $y\in \Sigma^*$, if $|y| \geq m$, consider all $m$ prefix of y, according to pigeon hole principle, there must be two prefix $u$ and $ux$ belong to the same equivalence class, then we can easily have:

\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\end{enumerate}

Since $\sim$ is an equivalence relation that is both left and right invariant, we can have:

\begin{enumerate}
\item[(3)]
For all $\alpha, \beta\in \Sigma^*$,
\[\alpha u\beta \in L
\quad\hbox{iff}\quad
\alpha ux^i \beta\in L\]
for all $i\geq 0$.
\end{enumerate}

\medskip
(v)
Prove that the converse of the pumping lemma in (iv) also holds,
i.e., if a language $L$ satisfies the pumping lemma in (iv),
then it is regular.\\

\noindent
\textbf{(v) Proof:}\\

Since the language satisfies the pumping lemma in (iv), it also satisfies the following equivalent statement:\\

There is some $m \geq 1$ so that for every $y\in \Sigma^*$, if $|y| \geq m$, then there exist $u, x, v\in \Sigma^*$ so that:

\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\item[(3)]
For all $\alpha, \beta, v \in \Sigma^*$,
\[\alpha uv\beta \in L
\quad\hbox{iff}\quad
\alpha ux^iv \beta\in L\]
for all $i\geq 0$.
\end{enumerate}

Similar to property (3), we can define an equivalence relationship:

\begin{center}
$u \sim v$ if and only if, for all $\alpha, \beta\in \Sigma^*$, $\alpha u\beta \in L \quad\hbox{iff}\quad \alpha v \beta\in L$
\end{center}

We can easily see that $\sim$ is an right invariant equivalence relation.\\

(1) For all string $y' \in L$, $|y'|<m$, they belong to at most $|\Sigma|^m$ equivalence classes in $\sim$.\\

(2) For all string $y \in L$, $|y| \geq m$, since pumping lemma hold, there exits $y=uxv$, for all $\alpha, \beta\in \Sigma^*$, $\alpha uv\beta \in L \quad\hbox{iff}\quad \alpha uxv \beta\in L$, and $|uv|<|y|$, by recursively apply such method, we can find $y' \in L$, $|y'|<m$, and $y \sim y'$. \\

With (1)(2), then we have $L$ belong to the union of finite index of equivalence classes in $\sim$\\

(3) For every equivalence class $C_{\sim}$ in $\sim$, if there exits one string $y \in C_{\sim}$ and $y \in L$, since $\sim$ is right invariant and property (3) hold, then we have all the strings in $C_{\sim}$ belong to $L$.\\

With (1)(2)(3), then we have $L$ is equal to the union of finite index of equivalence classes in $\sim$.\\ 

According to \textbf{Myhill-Nerode Theorem}, $L$ is regular language.\\

\vspace{0.25cm}\noindent
{\bf Problem B2.} \\

\noindent \textbf{Proof:}\\

Firstly, we prove that:

\begin{center} $\delta_R^*(T, w) = \{q\in Q \mid
\delta^*(q, w^R) \in T\} \cdot\cdot\cdot$ (1)\end{center}

\noindent Denote $T_1=\delta_R^*(T, w)$ and $T_2=\{q\in Q \mid
\delta^*(q, w^R) \in T\}$.
\begin {enumerate}
    \item Prove that $\forall q_1\in T_1$, $q_1\in T_2$. Suppose
    not, then $\exists q\in T$ so that $q_1=\delta^*_R(q,w)$ and $q_1$ does not belong to
    $T_2=\{q\in Q \mid
\delta^*(q, w^R) \in T\}$, which means:
    \begin{center} $\delta^*(q_1,w^R)$ does not belong to T
    $\cdot\cdot\cdot$(2) \end {center}
    From $q_1=\delta^*_R(q,w)$, $q\in T$ we have:
    \begin{center} $q=\delta^*(q_1,w^R)\in T$
    $\cdot\cdot\cdot$(3) \end{center}
    See that (2) contradicts with (3), so the suppose does not hold.
    We have $\forall q_1\in T_1$, $q_1\in T_2$.

    \item Prove that $\forall q_2\in T_2$, $q_2\in T_1$. Suppose
    $q_2$ does not belong to $T_1$, since $T_1=\delta_R^*(T, w)$, then:
    \begin{center} $q_2$ does not belong to $\delta_R^*(T,
    w)\cdot\cdot\cdot$ (4) \end{center}
    From $q_2\in T_2=\{q\in Q \mid \delta^*(q, w^R) \in T\}$, we
    have $\delta^*(q_2,w^R)\in T$, which means:
    \begin{center} $q_2\in \delta^*_R(T,w) \cdot\cdot\cdot$ (5)\end{center}
    See that (4) contradicts with (5), so the suppose does not hold.
    We have $\forall q_2\in T_2$, $q_2\in T_1$.
\end {enumerate}
From the discussion above, we can prove (1). Now we will prove that:
    \begin{center} $\forall$ different states $T_1, T_2, T_3\in Q^R$, $\forall w\in L(D^R)$, if $\delta^*_R(T_1,w)=\{q\in Q \mid
\delta^*(q, w^R) \in T_1\}=T_3$, then $\delta^*_R(T_2,w)=\{q\in Q
\mid \delta^*(q, w^R) \in T_2\}\neq T_3
    \cdot\cdot\cdot$ (6)
    \end{center}
Suppose not, then $\delta^*_R(T_1,w)=\delta^*_R(T_2,w)$, $\{q\in Q
\mid \delta^*(q, w^R) \in T_1\}=\{q\in Q \mid \delta^*(q, w^R) \in
T_2\}$. Since $\delta^*$ is deterministic, we must have $T_1=T_2$,
which contradicts with that $T_1$ is different from $T_2$. Then we
can
prove that (6) holds.\\

\noindent From the subset construction we know that in $D^{RR}$,
there is only one final state, denoted as $S_F$. In further, since
$D^{RR}$ is got from $D^R$ by the same procedure that $D^R$ is got,
(6) also holds for $D^{RR}$, which means:
    \begin{center} $\forall S_1, S_2\in Q^{RR}$, $\forall w\in
    L(D^{RR})$, if $\delta^*_{RR}(S_1,w)=S_F$, then
    $\delta^*_{RR}(S_2, w)\neq S_F$.
    \end{center}
This means $\forall S_1, S_2\in Q^{RR}$, $S_1$ and $S_2$ are
distinguishable. So $D^{RR}$ is a minimal DFA.\\


\vspace{0.25cm}\noindent
{\bf Problem B3.} \\

\medskip\noindent
\textbf{(a) Proof:}

\begin{enumerate}
  \item \noindent Prove the k-step reachability relation: \newline
    Doing math induction on k.
    \begin{itemize}
      \item Base Case k = 0. We know $\Delta_D^0 = I$ and by definition, a state can only reach itself with 0 step, which means
            $\Delta_D^k(q_i, q_j) = 1$ iff $i = j$. That is exactly the property of identity matrix. So $\Delta_D^{0}$ gives the
            0 step reachability.
      \item Induction step. Assume $\Delta_D^k$ gives the k-step reachability, i.e., $\Delta_D^k(q_i, q_j) = 1$ iff 
            $\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$ with $|w| = k$. \newline

            By multiplication rule of matrix, we know $\Delta_D^{k+1}(q_i,q_j) = \sum_{x=0}^{n}\Delta_D^k(q_i,q_x)\Delta_D(q_x,q_j)$.
            \newline

            So $\Delta_D^{k+1}(q_i,q_j) = 1$ iff $\exists x \ni \Delta_D^k(q_i,q_x) = 1\ and\ \Delta_D(q_x,q_j) = 1$.\newline

            From induction hypothesis and definition of $\Delta_D(q_x,q_j)$: \newline

            $\Delta_D^k(q_i,q_x) = 1$ iff $\delta^*(q_i, w) = q_x$, for some string $w\in \Sigma^*$ with $|w| = k$. \newline

            $\Delta_D(q_x,q_j) = 1$ iff $(\exists a\in \Sigma)(\delta(q_x, a) = q_j)$. \newline

            Therefore we know $\Delta_D^{k+1}(q_i,q_j) = 1$ iff $\delta^*(q_i, w) = q_x$, for some string $w\in \Sigma^*$ with $|w| = k$
            and $(\exists a\in \Sigma)(\delta(q_x, a) = q_j)$.\newline

            $\delta^*(q_i, w) = q_x, \delta(q_x, a) = q_j \Leftrightarrow \delta^*(q_i, w') = q_j$, for some string $w' = wa \in \Sigma^*$ 
            with $|w'| = k + 1$. \newline

            Concludely, $\Delta_D^{k+1}(q_i,q_j) = 1$ iff $\delta^*(q_i, w') = q_j$, for some string $w'\in \Sigma^*$ with $|w'| = k + 1$.     
    \end{itemize}
    
  \item \noindent Prove there are only finitely many $\Delta_D^k$: \newline

    We know each $\Delta_D^k$ is a $n \times n$ boolean matrix, and clearly there are only $2^{n \times n}$ distinct $n \times n$ boolean matrix.
    Therefore, there are only finitely many (no more than $2^{n \times n}$) matrix $\Delta_D^k$.
    
  \item \noindent Prove that there is a smallest $k\leq n - 1$ so that $\Delta_D^{*[k]} = \Delta_D^{*[k + i]}$ for all $i\geq 1$.
  Let $\Delta_D^* = \Delta_D^{*[k]}$, for the above $k$. \newline

  By definition, $\Delta_D^{*[k + 1]} = \Delta_D^{*[k]} + \Delta_D^{k+1}$. Notice that boolean addition either flips 0's to 1's or maintains 0's,
  which means $\Delta_D^{*[k + 1]}$ ``inherits'' all 1's from $\Delta_D^{*[k]}$ and get new 1's from $ \Delta_D^{k+1}$. 
  That indicates $\Delta_D^{*[k + 1]}$ contains strictly more 1's than $\Delta_D^{*[k]}$.
  But we know each $\Delta_D^{*[k]}$ is $n \times n$ boolean matrix, so it may contain at most $n \times n$ 1's. Since there is a upper bound
  ($n \times n$) for such strict increase relationship, there should exist a smallest $k\leq n - 1$ so that $\Delta_D^{*[k]} = \Delta_D^{*[k + i]}$
   for all $i\geq 1$.
   
  \item \noindent Prove that $\Delta_D^*(q_i, q_j) = 1$ iff $\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$.\newline

  We know $\Delta_D^* = \Delta_D^{*[k]} = \sum_{i = 0}^n\Delta_D^i$, for $k$ we get from above. \newline

  So $\Delta_D^*(q_i,q_j) = 1$ iff $\exists x \leq k \ni \Delta_D^x(q_i,q_j) = 1$.
  From the reachability relationship we proved in 1, we know $\Delta_D^x(q_i,q_j) = 1$ iff $\delta^*(q_i, w) = q_j$, for some string 
  $w\in \Sigma^*$ with $|w| = x$.\newline

  Therefore, $\Delta_D^*(q_i, q_j) = 1$ iff $\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$.
\end{enumerate}


\medskip \noindent \textbf{(b) Proof:}\\

The big idea is find a right-invariant equivalence relation of finite index.
\begin{enumerate}
  \item \noindent Prove $L_{2^n}$ is regular.\\

    Assume $D = (Q,\Sigma,\delta,q_0,F)$ is a DFA accepting L. Define a equivalence relation as follows:
    \begin{center}
    $u \equiv v$ iff $\delta^*(q_0,u)  = \delta^*(q_0,v)$ and $\Delta_D^{2^{|u|}} = \Delta_D^{2^{|v|}}$
    \end{center}
    First we prove such equivalence relation is right-invariant and has finite indexes.
    \begin{itemize}
      \item right-invariant: if $u \equiv v$, , we show $uw \equiv vw \forall w \in \Sigma^*$.\\

      By definition $\delta^*(q_0,u)  = \delta^*(q_0,v)$ and 
      $\Delta_D^{2^{|u|}} = \Delta_D^{2^{|v|}}$.\newline

      $\delta^*(q_0,u)  = \delta^*(q_0,v) \Rightarrow \delta^*(q_0,uw)  = \delta^*(q_0,vw)$. \newline

      $\Delta_D^{2^{|uw|}} = \Delta_D^{2^{|u| + |w|}} = \Delta_D^{2^{|u|}2^{|w|}} = {(\Delta_D^{2^{|u|}})}^{2^{|w|}} 
      = {(\Delta_D^{2^{|u|}})}^{2^{|w|}} = {(\Delta_D^{2^{|v|}})}^{2^{|w|}} = \Delta_D^{2^{|vw|}}$ \newline

      $\delta^*(q_0,uw)  = \delta^*(q_0,vw)$ and $\Delta_D^{2^{|uw|}} = \Delta_D^{2^{|vw|}}$ $\rightarrow$ $uw \equiv vw$
      
      \item finite index: There are two conditions for the equivalence relation we defined above. \newline 

      First condition $\delta^*(q_0,u)  = \delta^*(q_0,v)$ partitioned the $\Sigma^*$ into finitely many classes, because
      each $\delta^*(q_0,u)$ correspond to a state in D and there are finitely many states in DFA. \newline

      Second condition $\Delta_D^{2^{|u|}} = \Delta_D^{2^{|v|}}$ can been seen as a further refinement to the finite classes partitioned
      by first condition. We show this step is also finite indexed by noticing there are finitely many matrix $\Delta_D^k$, as we proved
      in (a)(1). \newline

      Concludely, the equivalence classes we obtain from the relation we define is finite indexed.        
    \end{itemize}
    Next we prove $L_{2^n}$ is the union of some of the equivalence classes we get from above. We already know the equivalence classes
    are partition of $\Sigma^*$, which implies every string in $L_{2^n}$ belongs to some equivelance class.The only thing we need to do
    is for each block, if there exists a string in $L_{2^n}$, then the entire block is in $L_{2^n}$. This can be done by proving the following
    lemma:\\

    \textbf{Lemma}: if $u \equiv v$ and $u \in L_{2^n}$, then $v \in L_{2^n}$. \\

    Proof: $u \equiv v \leftrightarrow \delta^*(q_0,u)  = \delta^*(q_0,v)$ and $\Delta_D^{2^{|u|}} = \Delta_D^{2^{|v|}}$.\\

    $u \in L_{2^n}$ means $\exists w \in \Sigma^* \ni |w| = 2^{|u|}\ \hbox{and}\ uw \in L$. $\delta^*(q_0,u)  = \delta^*(q_0,v)$, 
    assume $\delta^*(q_0,u)$ is the k-th state in D. Recall that the k-th row of $\Delta_D^{2^{|u|}}$ gives the $2^{|u|}$ steps reachability
    relation on D, starting from k-th state, which is $\delta^*(q_0,u)$. Hence, $uw \in L$ implies the k-th row of $\Delta_D^{2^{|u|}}$ 
    contains at least one 1 to a final state, which indicates there exists a $2^{|u|}$ steps path from $\delta^*(q_0,u)$ to a final state.\\

    Notice that $\Delta_D^{2^{|u|}} = \Delta_D^{2^{|v|}}$ and $\delta^*(q_0,u)  = \delta^*(q_0,v)$, so the same meaning also 
    applies to $v$, which means there exists a $2^{|v|}$ steps path, say $w'$, from $\delta^*(q_0,v)$ to a final state. 
    Therefore, $vw \in L$. Lemma proved.  
    
  \item \noindent Prove $L_{2^{2^n}}$ is regular.\\

  This is done by similarity. The entire process is highly similar to how we prove $L_{2^n}$ is regular. Define a equivalence relation as follows:
    \begin{center}
    $u \equiv v$ iff $\delta^*(q_0,u)  = \delta^*(q_0,v)$ and $\Delta_D^{2^{2^{|u|}}} = \Delta_D^{2^{2^{|v|}}}$
    \end{center}
    First we prove such equivalence relation is right-invariant and has finite indexes, which is basically a replay of what we do for (1).\\

    Second we show $L_{2^{2^n}}$ is the union of some of the equivalence classes we get from above, which is exactly the same as (1).
\end{enumerate}

\medskip \noindent \textbf{(c) Proof:}\\

The big idea is find a right-invariant equivalence relation of finite index, which is exactly the same as we did in (b).\\
In fact, the entire proof is just the same as (b), except just a little differences on how we define the equivalence relation
and how we proof the right-invariant property.\\

Define a equivalence relation as follows:
    \begin{center}
    $u \equiv v$ iff $\delta^*(q_0,u)  = \delta^*(q_0,v)$, $\Delta_D^{|u|^2} = \Delta_D^{|v|^2}$ and $\Delta_D^{|u|} = \Delta_D^{|v|}$.
    \end{center}
First we prove such equivalence relation is right-invariant and has finite indexes. The finite index proof is just a replay of what we did
for (b)(1). So we only focus on proving the right-invariant propert here.\\

if $u \equiv v$, we show $uw \equiv vw \forall w \in \Sigma^*$.\\

By definition $\delta^*(q_0,u)  = \delta^*(q_0,v)$, $\Delta_D^{|u|^2} = \Delta_D^{|v|^2}$ and $\Delta_D^{|u|} = \Delta_D^{|v|}$.\\

$\delta^*(q_0,u)  = \delta^*(q_0,v) \Rightarrow \delta^*(q_0,uw)  = \delta^*(q_0,vw)$. \newline

$\Delta_D^{|uw|^2} = \Delta_D^{{(|u| + |w|)}^2} = \Delta_D^{|u|^2 + 2|u||w| + |w|^2} = \Delta_D^{|u|^2}\Delta_D^{2|u||w|}\Delta_D^{|w|^2}$
$\Delta_D^{|u|^2} = \Delta_D^{|v|^2}$ and $\Delta_D^{|u|} = \Delta_D^{|v|}$ $\Rightarrow \Delta_D^{|u|^2}\Delta_D^{2|u||w|}\Delta_D^{|w|^2}
= \Delta_D^{|v|^2}\Delta_D^{2|v||w|}\Delta_D^{|w|^2} = \Delta_D^{|vw|^2}$. So $\Delta_D^{|uw|^2} = \Delta_D^{|vw|^2}$.\\

$\Delta_D^{|u|} = \Delta_D^{|v|} \Rightarrow \Delta_D^{|uw|} = \Delta_D^{|u| + |w|} = \Delta_D^{|u|}\Delta_D^{|w|} 
= \Delta_D^{|v|}\Delta_D^{|w|} = \Delta_D^{|v| + |w|} = \Delta_D^{|vw|}$\\

Therefore, $uw \equiv vw$, which means right-invariant holds.\\

Next step is prove $L_{n^2}$ is the union of some of the equivalence classes we get from above. This proof is exactly the same as what we did in (b)(1), because the way how we define the equivalence relationship is just the same as we did in (b)(1). And finally, we reach the fact that $L_{n^2}$ is regular.\\

\medskip \noindent \textbf{(d) Proof:}\\

For the same reason as (c), the big picture is exactly the same as the proof of (b)(1). We only focus on the slightly different part, which is 
define the equivalence relationship and show the right-invariant property.\\

Define a equivalence relation as follows:
    \begin{center}
    $u \equiv v$ iff $\delta^*(q_0,u)  = \delta^*(q_0,v)$, and $ \forall i \in \natnums, \ 0 \leq i \leq n,\ \Delta_D^{|u|^i} = \Delta_D^{|v|^i}$.
    \end{center}
One thing we need to emphysis is that from this definition, it immediately follows the fact that $u \equiv v \rightarrow P(|u|) = P(|v|)$. So
the way we define the equivalence is still derived from $L_P$, which is why we can claim that all the rest of this proof is exactly the same as (b)(1).\\

Next we prove the right-invariant property:\\

If $u \equiv v$, we show $uw \equiv vw \forall w \in \Sigma^*$.
\begin{itemize}
 \item $\delta^*(q_0,u)  = \delta^*(q_0,v) \Rightarrow \delta^*(q_0,uw)  = \delta^*(q_0,vw)$.
 \item we prove $ \forall i \in \natnums, \ 0 \leq i \leq n, \Delta_D^{|uw|^i} = \Delta_D^{|vw|^i}$ by using the binomial expanded form. 
  Notice $\Delta_D^{|uw|^i} = \Delta_D^{(|u| + |w|)^i}$, recall that $ \forall i \in \natnums, \ 0 \leq i \leq n,\ \Delta_D^{|u|^i} =
  \Delta_D^{|v|^i}$, it follows from binomial expanded theorem that $\Delta_D^{|uw|^i} = \Delta_D^{(|u| + |w|)^i} = \Delta_D^{(|v| + |w|)^i}
  =\Delta_D^{|vw|^i}$
\end{itemize}
Therefore the right-invariant property holds. We can stop and finish our proof here, because the rest of the proof is no more than replay of what we did in (b)(1), i.e., prove $L_P$ is the union of some of the equivalence classes we get from above. And finally, we reach the fact that $L_P$ is regular.\\

\vspace{0.25cm}\noindent
{\bf Problem B4.} \\

\noindent
\textbf{(a) Proof:}\\

CFG is shown below:

\begin{itemize}
\item (1) $S \rightarrow aSa$
\item (2) $S \rightarrow bSb$
\item (3) $S \rightarrow c$
\end{itemize}

Justification:\\

(1) For every string $w'=wcw^R \in L_5$, apply rule (1)(2) respectively, according to the occurance of $a,b$ in $w$, and finally apply rule (3), we can have every string $w' \in L_5$ can be generated by our CFG.\\

(2) Rule(1)(2) make sure all the strings generated by the CFG are in the form: $w'=wSw^R$, rule (3) make sure all the strings generated by the CFG have $c$ in the middle.\\

\noindent
\textbf{(b) Proof:}\\

CFG is shown below:

\begin{itemize}
\item (1) $S \rightarrow aS_0bS_1$
\item (2)(3) $S_0 \rightarrow aS_0bS_1 | \epsilon$
\item (4)(5) $S_1 \rightarrow b | \epsilon$
\end{itemize}


Justification:\\

(1) For every string $w'=a^mb^n \in L_6$, firstly apply rule (1), apply rule (2) $m-1$ times, then apply rule (4) $n-m$ times, and finally apply rule (3) or (5), we can have every string $w' \in L_6$ can be generated by our CFG.\\

(2) Rule(1)(2) make sure all the strings $w$ generated by the CFG have $m,n \geq 1$ and are in form $a^mb^{m+i}$, along with rule (4) make sure $w=a^mb^{m+i}$ and $i \leq m$, rule (3)(5) make sure the grammar can finish.\\

\medskip
For any fixed integer $K\geq 2$, $L_{7} = \{a^{m}b^{n}\ \mid\ 1 \leq m \leq n \leq Km\}$\\

\noindent
\textbf{(b') Proof:}\\

CFG is shown below:


\begin{itemize}
\item (1) $S \rightarrow aS_0b\underbrace{S_1 \cdots S_1}_{k}$
\item (2)(3) $S_0 \rightarrow aS_0b\underbrace{S_1 \cdots S_1}_{k} | \epsilon$
\item (4)(5) $S_1 \rightarrow b | \epsilon$
\end{itemize}


Justification:\\

(1) For every string $w'=a^mb^n \in L_7$, firstly apply rule (1), apply rule (2) $m-1$ times, then apply rule (4) $n-m$ times, and finally apply rule (3) or (5), we can have every string $w' \in L_7$ can be generated by our CFG.\\

(2) Rule(1)(2) make sure all the strings $w$ generated by the CFG have $m,n \geq 1$ and are in form $a^mb^{m+i}$, along with rule (4) make sure $w=a^mb^{m+i}$ and $i \leq (K-1)m$, rule (3)(5) make sure the grammar can finish.\\

\noindent
\textbf{(c) Proof:}\\

CFG is shown below:

\begin{itemize}
\item (1)(2) $S \rightarrow aS_0b|aS_1bb$,
\item (3)(4) $S_0 \rightarrow aS_0b | \epsilon$,
\item (5)(6) $S_1 \rightarrow aS_1bb | \epsilon$,\\
\end{itemize}


Justification:\\

(1) For every string $w'=a^nb^n \in L_8$, firstly apply rule (1), apply rule (3) $n-1$ times, finally apply rule (4); for every string $w'=a^nb^{2n} \in L_8$, firstly apply rule (2), apply rule (5) $n-1$ times, finally apply rule (6). We can have every string $w' \in L_8$ can be generated by our CFG.\\

(2) Rule(1)(3)(4) make sure CFG generate strings $w$ in form $a^nb^{n}$, (2)(5)(6) make sure CFG generate strings $w$ in form $a^nb^{2n}$, rule(4)(6) make sure the CFG can finish generating.\\

\noindent
\textbf{(d) Proof:}\\

CFG is shown below:

\begin{itemize}
\item (1)(2) $S \rightarrow aS_0abS_{00}|aS_{10}bbbbS_1bbbb$
\item (3)(4) $S_0 \rightarrow aS_0a | bS_{00}$
\item (5)(6) $S_{00} \rightarrow bS_{00} | \epsilon$
\item (7)(8) $S_1 \rightarrow bbbbS_1bbbb | aS_{10}$
\item (9)(10) $S_{10} \rightarrow aS_{10} | \epsilon$
\end{itemize}

Justification:\\

(1) For every string $w'=a^mb^na^mb^p \in L_9$, firstly apply rule (1), apply rule (3) $m-1$ times, apply rule (4), then apply rule (5) $p+n-2$ times, finally apply (6) twice; for every string $w'=a^mb^{4n}a^pb^{4n} \in L_9$, firstly apply rule (2), apply rule (7) $n-1$ times, apply rule (8), then apply rule (9) $p+m-2$ times, finally apply (10) twice;. We can have every string $w' \in L_9$ can be generated by our CFG.\\

(2) Rule(1)(3)(4)(5)(6) make sure CFG generate strings $w$ in form $a^mb^na^mb^p$, (2)(7)(8)(9)(10) make sure CFG generate strings $w$ in form $a^mb^{4n}a^pb^{4n}$, rule(6)(10) make sure the CFG can finish generating.\\

\noindent
\textbf{(e) Proof:}\\

CFG is shown below:

\begin{itemize}
\item (1)(2) $S \rightarrow S_1S_1SS_1 | c$
\item (3)(4) $S_1 \rightarrow a | b$
\end{itemize}

Justification:\\

(1) For every string $w'=xcy \in L_{10}$, apply rule (1) $|y|$ times, apply rule (3)(4) respectively according to the occurance of $a,b$ in $x, y$, and finally apply rule (2), we can have every string $w' \in L_{10}$ can be generated by our CFG.\\

(2) Rule(1) make sure all the strings generated by the CFG are in the form: $w'=|x|S|y|$, and $|x|=2|y|$, rule (2) make sure all the strings generated by the CFG have $c$ in the middle.\\

\vskip 0.25cm \noindent
{\bf Problem B5.} 

\vskip 0.25cm \noindent
\medskip\noindent
\textbf{Proof:} Without loss of generality, assume
that $L = L(G)$, where $G = (V, \Sigma, P, S)$ is in Chomsky normal form,
and let $R = L(D)$, for some DFA $D = (Q, \Sigma, \delta, q_0, F)$.
Use a cross-product construction
as sketched below:\\

Construct a CFG $G_2$ whose set
of nonterminals is $Q\times N\times Q\ \cup\{S_0\}$,
where $S_0$ is a new nonterminal, and whose productions are
of the form:\\

\begin{enumerate}
 \item for every $f\in F$, $$S_0 \rightarrow (q_0, S, f)$$
 \item for all $a\in \Sigma$, all $A\in N$,  and all $p\in Q$, $$(p, A, \delta(p, a)) \rightarrow a \quad\hbox{iff}\quad (A \rightarrow a) \in P$$
 \item for all $p, q, s\in Q$ and all $A, B, C\in N$, $$(p, A, s) \rightarrow (p, B, q)(q, C, s) \quad\hbox{iff}\quad (A \rightarrow BC)\in P$$
 \item $$S_0 \rightarrow \epsilon  \quad\hbox{iff}\quad (S\rightarrow \epsilon) \in P\ \hbox{and}\ q_0\in F$$
\end{enumerate}

\medskip
In the next, we will prove that
for all $p, q\in Q$, all $A\in N$, all $w\in\Sigma^+$, and all $n\geq 1$,
$$(p, A, q) \lmder{n}_{G_{2}} w \quad\hbox{iff}\quad A \lmder{n}_{G} w\quad \hbox{and}\quad \delta^*(p, w) = q.$$

First of all, We observe from the contruction above, all the grammar rules in CFG $G_2$ (except $S_0 \rightarrow \epsilon  \quad\hbox{iff}\quad (S\rightarrow \epsilon) \in P\ \hbox{and}\ q_0\in F$) are in CNF. Meanwhile, it is easy to see that all the string $w$ with $|w|=n$ generated by a CNF grammar will need $2n-1$ steps of derivations, which include using $n-1$ steps of rules in $A \rightarrow BC$ form, and $n$ steps of rules in $A \rightarrow a$ form. In another word, if $(p, A, q) \lmder{n}_{G_{2}} w$ and $w \in \Sigma^*$, then $n$ must be a odd number.\\

Assume the length of string $w$ is $i$.
\begin{itemize}
 \item when $i=1$, according to the construction rule (2) above we have, for all $a\in \Sigma$, all $A\in N$,  and all $p\in Q$, $(p, A, \delta(p, a)) \rightarrow a \quad\hbox{iff}\quad (A \rightarrow a) \in P$. That is to say: $(p, A, q) \lmder{1}_{G_{2}} w$ iff $ A \lmder{1}_{G} $ and $\delta(p, w) = q$.
 \item Let us assume when $i \leq n$, we have:
 $$(p, A, q) \lmder{2i-1}_{G_{2}} w \quad\hbox{iff}\quad A \lmder{2i-1}_{G} w\quad \hbox{and}\quad \delta^*(p, w) = q.$$
 \item When $i=n+1$, using induction hypothesis, we have:
 $$(p, A, q) \lmder{2i-1}_{G_{2}} w'(p_1, B, p_2)(p_2, C, q) \quad\hbox{iff}\quad A \lmder{2i-1}_{G} w'BC \quad \hbox{and}\quad \delta^*(p, w') = p_1.$$

Denote $w$ = $w'uv$, $u, v \in \Sigma$, keep using the rules in CFG $G_2$ twice, we can have:
 $$(p, A, q) \lmder{2i}_{G_{2}} w'u(p_2, C, q) \quad\hbox{iff}\quad A \lmder{2i}_{G} w'uC \quad \hbox{and}\quad \delta^*(p, w'u) = p_2.$$
 $$(p, A, q) \lmder{2i+1}_{G_{2}} w'uv \quad\hbox{iff}\quad A \lmder{2i+1}_{G} w'uv \quad \hbox{and}\quad \delta^*(p, w'uv) = q.$$

Which is equivalent to:
$$(p, A, q) \lmder{2i+1}_{G_{2}} w \quad\hbox{iff}\quad A \lmder{2i+1}_{G} w\quad \hbox{and}\quad \delta^*(p, w) = q.$$
\end{itemize}

By induction, we have the proof. Then we can see:\\

(1) When $w=\epsilon$, according to the construction above we have $S_0 \rightarrow \epsilon$ iff $(S\rightarrow \epsilon) \in P$ and $q_0\in F.$ That is to say: $w \in L(G_2) \quad\hbox{iff}\quad w \in L \quad\hbox{and}\quad w \in R$.\\

(2) for all the string $w neq \epsilon$, using the result of the proof above, let $p = q_0$, $A = S$, $q = f, f \in F$, then we have:
$$(q_0, S, f) \lmder{n}_{G_{2}} w \quad\hbox{iff}\quad S \lmder{n}_{G} w\quad \hbox{and}\quad \delta^*(q_0, w) = f$$

With(1)(2), we conclude that $L(G_2) = L \cap R $.


\vspace{0.5cm}\noindent

\end{document}
 
